# n=2
n=5
#使用笨方法先求解一遍
def countBits(n):
    ans=[0 for _ in range(n+1)]

    for i in range(1,n+1):
        n=i
        count=0
        while n!=0:
            count+=n&1
            n>>=1
        ans[i]=count
    print(ans)
# countBits(n)

#位运算结合动态规划进行求解
def countBits1(n):
    dp=[0 for _ in range(n+1)]

    for i in range(1,n+1):
        if i&1==1:
            #最后一位是1
            dp[i]=dp[i-1]+1
        else:
            #最后一位是1
            dp[i]=dp[i>>1]
    print(dp)
countBits1(n)